package com.cyy.test_t_3_;
/**
 * 剑指Offer 面试题30
 * 最小的K个数
 * 时间限制：1秒 空间限制：32768K
 * 题目描述:
 * 输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，
 * 则最小的4个数字是1,2,3,4,。
 */
import java.util.ArrayList;

public class t_30 {
	
	public static void main(String []args){
		int []a = {4,5,1,6,2,7,3,8};
		System.out.println(GetLeastNumbers_Solution(a,10));
	}
	
	public static ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        int len = input.length;
        ArrayList<Integer> result = new ArrayList<>(); 
        
		if(input == null || len<=0 || k <= 0 || k > len){
        	return result;
        }
		
        
        for(int i=0;i<k;i++){
        	for(int j=0;j < len - i-1;j ++){
    			if(input[j] < input[j+1]){
    				int tmp = input[j];
    				input[j] = input[j+1];
    				input[j+1] = tmp;
    			}
    		}
        	result.add(input[len-i-1]);
        }
		return result;
    }
	
}
